package class04

type BSTNode struct {
	Val   int
	Left  *BSTNode
	Right *BSTNode
}

/*
	双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left，right
	认为是next的话。
	给定一个搜索二叉树头节点head，请转化成一条有序的双向链表，并返回链表的头
	节点。
*/
func convert(head *BSTNode) *BSTNode {
	return ConvertProcess(head).head
}

type Info struct {
	head *BSTNode
	tail *BSTNode
}

func ConvertProcess(node *BSTNode) Info {
	if node.Left == nil && node.Right == nil {
		return Info{head: node, tail: node}
	}
	var leftInfo Info
	var rightInfo Info
	if node.Left != nil {
		leftInfo = ConvertProcess(node.Left)
	}
	if node.Right != nil {
		rightInfo = ConvertProcess(node.Right)
	}
	var curHead, curTail *BSTNode
	if leftInfo.head == nil {
		curHead = node
	} else {
		curHead = leftInfo.head
		leftInfo.tail.Right = node
		node.Left = leftInfo.tail
	}
	if rightInfo.head == nil {
		curTail = node
	} else {
		curTail = rightInfo.tail
		node.Right = rightInfo.head
		rightInfo.head.Left = node
	}
	return Info{curHead, curTail}
}
